class RangeFreqQuery {
public:
    RangeFreqQuery(vector<int>& arr)
    {
        for (int i = 0; i < arr.size(); i++)
        {
            a.push_back(arr[i]);
            hash[arr[i]].push_back(i);
        }
    }

    int query(int left, int right, int value)
    {
        int cnt = 0;
        int l = lower_bound(hash[value].begin(), hash[value].end(), left) - hash[value].begin(), r = upper_bound(hash[value].begin(), hash[value].end(), right) - hash[value].begin();
        if (l == hash[value].size()) return 0;
        return r - l;
    }
private:
    vector<int> a;
    unordered_map<int, vector<int>> hash;
};

/**
 * Your RangeFreqQuery object will be instantiated and called as such:
 * RangeFreqQuery* obj = new RangeFreqQuery(arr);
 * int param_1 = obj->query(left,right,value);
 */